// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-01 14:14
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

@SuppressWarnings("ALL")
/**
 * 线段树类（堆式存储）
 * 1 查询
 * 2 更新（插值）
 * 3 构造
 */
public class SegmentTreeT<E> {
    private int size;
    private Node[] data;
    public Merger<E> merger;



    public void setMerger(Merger<E> merger) {
        this.merger = merger;
    }

    public SegmentTreeT(Merger<E> merger, E[] source) {
        this.size = source.length;
        this.merger = merger;
        this.data = new Node[4 * size];
        buildTree(0, source, 0, source.length - 1);
    }

    class Node<E> {
        E value;
        int left, right;

        public Node(E value, int left, int right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 线段树构建:将sourcu里面的数据映射到线段树中
     */
    public void buildTree(int treeIndex, E[] source, int left, int right) {
        if (left == right) {
            // 原数据只有一个元素，当前节点创建为叶子节点
            data[treeIndex] = new Node(source[left], left, right);
            return;
        }
        // 需要创建的数据多于一个，需要分区间进行创建
        int leftChildIndex = leftChild(treeIndex), rightChildIndex = rightChild(treeIndex);
        Node root = data[treeIndex];
        int middle = root.left + ((root.right - root.left) >> 1);
        // 创建区域在根节点左子树
        buildTree(leftChildIndex, source, left, middle);
        // 创建节点在根节点右子树
        buildTree(rightChildIndex, source, middle + 1, right);
        // 创建非叶子节点
        data[treeIndex] = new Node(merger.merge(elementData(leftChildIndex), elementData(rightChildIndex)), left, right);
    }

    /**
     * 线段树插值
     */
    public void update(E value, int left, int right) {
        if (left < right || left < 0 || left > size || right < 0 || right > size) {
            throw new IllegalArgumentException("Illegal Argument!");
        }
        update(0, value, left, right);
    }

    public void update(int treeIndex, E value, int left, int right) {
        Node root = data[treeIndex];
        if (root.left == left && root.right == right) {
            // 当前根节点和需要创建节点重合
            root.value = value;
            return;
        }
        int middle = root.left + ((root.right - root.left) >> 1);
        int rightChildIndex = rightChild(treeIndex), leftChildIndex = leftChild(treeIndex);
        if (middle > right) {
            update(rightChildIndex, value, left, right);
        } else {
            update(leftChildIndex, value, left, right);
        }
        // 更新非叶子节点的数值
        data[treeIndex].value = merger.merge(elementData(rightChildIndex), elementData(leftChildIndex));
    }


    /**
     * 线段树的查询操作
     */
    public E search(int left, int right) {
        if (left < right || left < 0 || left > size || right < 0 || right > size) {
            throw new IllegalArgumentException("Illegal Argument!");
        }
        return search(0, left, right);
    }

    public E search(int treeIndex, int left, int right) {
        Node root = data[treeIndex];
        if (root.left == left && root.right == right) {
            return (E) root.value;
        }
        int middle = root.left + ((root.right - root.left) >> 1);
        int rightChildIndex = rightChild(treeIndex), leftChildIndex = leftChild(treeIndex);
        if (middle > right) {
            return search(leftChildIndex, left, right);
        } else if (middle < left) {
            return search(rightChildIndex, left, right);
        }
        // 需要进行分区间查询（为了实现区域查询）
        E leftAreaValue = search(leftChildIndex, left, middle);
        E rightAreaValue = search(rightChildIndex, middle + 1, right);
        return merger.merge(leftAreaValue, rightAreaValue);
    }

    public int leftChild(int index) {
        return 2 * index + 1;
    }

    public int rightChild(int index) {
        return 2 * index + 2;
    }

    public E elementData(int treeIndex) {
        return (E) data[treeIndex].value;
    }


    public interface Merger<E> {
        E merge(E a, E b);
    }

}
